package SortSearch;

import Interfaces.SortableElements;

/**
 * This class implements the Quick Sort<br>
 * See also:<br>
 * <a href="//http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm">http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm</a>
 * 
 * @author Stefan Lorenz<br>
 * <br>26.11.2012
 */
public class QuickSorter implements Runnable {
    
    private SortableElements[] a;
    private int n;
    
    
    public QuickSorter(SortableElements[] a) {
	this.a = a;
    }

    public void sort(SortableElements[] a) {	
        this.a=a;
        n=a.length;
        quicksort(0, n-1);
        
    }

    private void quicksort (int lo, int hi){
        int i=lo, j=hi;
        // Vergleichs­element x
        SortableElements x= a[(lo+hi)/2];

        //  Aufteilung
        while (i<=j) {    
            while (a[i].getStart()<x.getStart()) i++; 
            while (a[j].getStart()>x.getStart()) j--;
            if (i<=j)
            {
                exchange(i, j);
                i++; j--;
            }
        }
        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    private void exchange(int i, int j) {
	SortableElements t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public void setA(SortableElements[] a) {
	this.a = a;
    }

    public SortableElements[] getA() {
	return a;
    }


    public void run() {
		sort(this.a);
    } 
}